package com.yuren.codecrushlearn.Q5400;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 * dfs
 * @author 10204
 * @date 2025-06-15 23:53
 */
public class Q5453 {
    public boolean found;
    public List<Integer> visited;
    public int v;
    public List<List<Integer>> adj;

    public Q5453(List<List<Integer>> edges, int e, int v) {
        this.found = false;
        this.v = v;
        this.visited = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            this.visited.add(0);
        }
        this.adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            this.adj.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            this.addEdge(edge.get(0), edge.get(1));
        }
    }

    public void addEdge(int v1, int v2) {
        this.adj.get(v1).add(v2);
    }

    public boolean reach(int s, int t) {
        this.found = false;
        this.dfs(s, t);
        return this.found;
    }

    public void dfs(int s, int t) {
        if (this.found) return;
        this.visited.set(s, 1);

        if (s == t) {
            found = true;
            return;
        }

        for (int i = 0; i < adj.get(s).size(); i++) {
            int q = adj.get(s).get(i);
            if (this.visited.get(q) == 0) {
                this.dfs(q, t);
            }
        }
    }
}
